/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-06
 * Time: 16:56
 */
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val){
        this.val=val;
    }
}
public class BinarySearchTree {
    public Node root;

    /**
     * 查找某个值是否存在
     * @param val
     * @return
     */
    public boolean find(int val){
        Node cur=root;
        while(cur!=null){
            if(cur.val==val){
                return true;
            }else if(cur.val<val){
                cur=cur.right;
            }else {
                cur=cur.left;
            }
        }
        return false;
    }

    /**
     * 插入某个值
     * @param val
     * @return
     */
    public boolean insert(int val){
        if(root==null){
            root=new Node(val);
            return true;
        }
        Node parent=null;
        Node cur=root;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){
                //不能有相同的数据
                return false;
            } else {
                parent=cur;
                cur=cur.left;
            }
        }
        Node node=new Node(val);
        if(parent.val>val){
            parent.left=node;
        }else{
            parent.right=node;
        }
        return true;
    }

    public boolean remove(int val){
        Node temp=root;
        Node cur=root;
        Node parent=null;
        //先找到这个值
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }else{
                //找到这个值
                //分三种情况
                //一:cur左边为空
                if(cur.left==null){
                    //再分三种情况
                    if(cur==root){
                        root=root.right;
                    }else{
                        if(cur==parent.left){
                            parent.left=cur.right;
                        }else{
                            parent.right=cur.right;
                        }
                    }
                }else if(cur.right==null){
                    //二:cur右边为空
                    //也再分三种情况
                    if(cur==root){
                        root=root.left;
                    }else{
                        if(cur==parent.left){
                            parent.left=cur.left;
                        }else{
                            parent.right=cur.left;
                        }
                    }
                }else {
                    //左右两边都不为空
                    //刚开始targeParent初始值必须为cur
                    //避免出现左子树或右子树只有一个节点
                    Node targetParent=cur;
                    Node target=cur.left;
                    //开始找替罪羊(右子树最小或者左子树最大,这里以左子树最大为例)
                    while(target.right!=null){
                        targetParent=target;
                        target=target.right;
                    }
                    //找到替罪羊了
                    //先替换
                    cur.val=target.val;
                    //再删除
                    if(target==targetParent.left){
                        //注意这里不能直接置为空.否则该节点后面的节点都没有了
                        targetParent.left=target.left;
                    }else{
                        targetParent.right=target.left;
                    }
                }
                return true;
            }
        }
        //没有找到这个值
        return false;
    }

    /**
     * 中序遍历
     * 二叉搜索树中序遍历有顺序
     * @param root
     */
    public void inOrder(Node root){
        if(root==null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
}
